package thired.class08_tree;

import java.util.concurrent.locks.ReadWriteLock;

public class Class06_isBalanceTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }
    public static class Info{
        public boolean isB;
        public int height;

        public Info(boolean l,int h){
            isB = l;
            height = h;
        }
    }
    public static boolean isBalanceTree(Node head){
        if(head == null){
            return true;
        }
        return process(head).isB;
    }

    public static Info process(Node node){
        if(node == null){
            return new Info(true,0);
        }
        Info left = process(node.left);
        Info right = process(node.right);
        boolean isb = true;
        if(!left.isB || !right.isB || Math.abs(left.height - right.height) > 1){
            isb = false;
        }
        int h = Math.min(left.height,right.height) + 1;
        return new Info(isb,h);
    }


    public static boolean isB2(Node head) {
        return process1(head).isB;
    }
    
    public static Info process1(Node x) {
        if(x == null) {
            return new Info(true, 0);
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int height = Math.max(leftInfo.height, rightInfo.height)  + 1;
        boolean isB = true;
        if(!leftInfo.isB) {
            isB = false;
        }
        if(!rightInfo.isB) {
            isB = false;
        }
        if(Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isB = false;
        }
        return new Info(isB, height);
    }






    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (isBalanceTree(head) != isB2(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

}
